package net.lainiao.leetcode;

import java.util.Arrays;
import java.util.List;

public class lintcode42 {
    //最大子数组II
    public static void main(String[] args) {
        Integer[] nums={1, 3, -1, 2, -1, 2};
        List<Integer> list= Arrays.asList(nums);
        int res=GetMaxSubArrayTwo(list);
        System.out.println(res);
    }

    private static int GetMaxSubArrayTwo(List<Integer> nums) {
        int size=nums.size();
        if(size<=2){
            if(size==1){
                return nums.get(0);
            }
            return nums.get(0)+nums.get(1);
        }
        int[] left=new int[size];
        int[] right=new int[size];
        int res=nums.get(0);
        int sum=res;
        left[0]=res;
        for (int i = 1; i <size ; i++) {
            if(sum<0){
                sum=nums.get(i);
            }else{
                sum+=nums.get(i);
            }
            if(sum>res){
                res=sum;
            }
            left[i]=res;
        }

        res=nums.get(size-1);
        sum=res;
        right[size-1]=res;
        for (int i = size-2; i >=0 ; i--) {
             if(sum<0){
                 sum=nums.get(i);
             }else{
                 sum+=nums.get(i);
             }
             if(sum>res){
                 res=sum;
             }
             right[i]=res;
        }
        res=Integer.MIN_VALUE;
        for (int i = 0; i <size-1 ; i++) {
            int tem=left[i]+right[i+1];
            if(tem>res){
                res=tem;
            }
        }

        return res;
    }
}
